package jp.co.worksap.recruiting;

/**
 * This class used a LinkedList to keep the queue in order. In the cause of get the Max, Min 
 * and the Median of the queue, I use Black-Red Tree to keep the element. The elements in 
 * lagerTree is lager than the ones in smaller tree. I use B-R Tree because it is convenient 
 * for Java.
 * 
 * 
 * @author chenmo
 * 
 */
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.TreeMap;

public class ExamPeekableQueueImpl<E extends Comparable<E>> implements
		ExamPeekableQueue<E> {

	/**
	 * @param args
	 */

	public ExamPeekableQueueImpl() {
	}

	private final Queue<E> queue = new LinkedList<E>();

	private final TreeMap<E, Integer> largerTree = new TreeMap<E, Integer>();
	private int largerTreeCount = 0;

	private final TreeMap<E, Integer> smallerTree = new TreeMap<E, Integer>();
	private int smallerTreeCount = 0;

	@Override
	public void enqueue(E e) {

		if (e == null) {
			throw new IllegalArgumentException();
		}
		queue.offer(e);

		if (largerTreeCount == 0) {
			addToLargerTree(e);
		} else if (e.compareTo(largerTree.firstKey()) > 0) {
			addToLargerTree(e);
		} else if (smallerTree.isEmpty()||e.compareTo(smallerTree.lastKey()) < 0) {
			addToSmallerTree(e);
		} else {
			addToLargerTree(e);
		}
		
		/*
		 * The difference between to trees couldn't larger than 2
		 */
		if (largerTreeCount == (smallerTreeCount + 2)) {
			addToSmallerTree(largerTree.firstKey());
			removeFromLargerTree(largerTree.firstKey());
		} else if (smallerTreeCount == (largerTreeCount + 2)) {
			addToLargerTree(smallerTree.lastKey());
			removeFromSmallerTree(smallerTree.lastKey());
		}

	}

	@Override
	public E dequeue() {

		if (queue.isEmpty()) {
			throw new NoSuchElementException();
		} else {
			E e = queue.remove();
			if (largerTree.get(e) == null) {
				removeFromSmallerTree(e);
			} else {
				removeFromLargerTree(e);
			}

			if (largerTreeCount == (smallerTreeCount + 2)) {
				addToSmallerTree(largerTree.firstKey());
				removeFromLargerTree(largerTree.firstKey());
			} else if (smallerTreeCount == (largerTreeCount + 2)) {
				addToLargerTree(smallerTree.lastKey());
				removeFromSmallerTree(smallerTree.lastKey());
			}
			return e;
		}

	}

	@Override
	public E peekMedian() {
		if (queue.isEmpty()) {
			throw new NoSuchElementException();
		}
		if (largerTreeCount >= smallerTreeCount) {
			return largerTree.firstKey();
		} else {
			return smallerTree.lastKey();
		}

	}

	@Override
	public E peekMaximum() {
		if (queue.isEmpty()) {
			throw new NoSuchElementException();
		} else {
			return largerTree.lastKey();
		}
	}

	@Override
	public E peekMinimum() {
		if (queue.isEmpty()) {
			throw new NoSuchElementException();
		} else {
			return smallerTree.firstKey();
		}

	}

	@Override
	public int size() {
		return largerTreeCount + smallerTreeCount;
	}

	public void addToLargerTree(E e) {
		if (largerTree.get(e) == null) {
			largerTree.put(e, 1);
		} else {
			largerTree.put(e, largerTree.get(e) + 1);
		}
		largerTreeCount++;
	}

	public void addToSmallerTree(E e) {
		if (smallerTree.get(e) == null) {
			smallerTree.put(e, 1);
		} else {
			smallerTree.put(e, smallerTree.get(e) + 1);
		}
		smallerTreeCount++;
	}

	public void removeFromLargerTree(E e) {
		if (largerTree.get(e) == 1) {
			largerTree.remove(e);
		} else {
			largerTree.put(e, largerTree.get(e) - 1);
		}
		largerTreeCount--;
	}

	public void removeFromSmallerTree(E e) {
		if (smallerTree.get(e) == 1) {
			smallerTree.remove(e);
		} else {
			smallerTree.put(e, smallerTree.get(e) - 1);
		}
		smallerTreeCount--;
	}

	public static void main(String[] args) {

	}

}
